package animation.sort.algorithms;

import animation.core.AlgorithmMonitorModel;


/**
 * Created by IntelliJ IDEA.
 * User: emilio
 * Date: Aug 12, 2004
 * Time: 11:57:23 AM
 * To change this template use File | Settings | File Templates.
 */
public class QSort3Partition
        extends MedianOf3QuickSort
{
    public String toString()
    {
        return "QSort (3-Partition)";
    }

    void sort(int array[], int low, int high)
            throws Exception
    {
        markBox(low, high);

        int n = high - low + 1;
        if (n <= 1) {
        }
        else if (n == 2) {
            swapIfGreater(array, low, high);
        }
        else {
            int m = (high + low) / 2;
            if (n == 3) {
                sort3(array, low, m, high);
            }
            else {
                sort3(array, low, high, m);
                partition3(array, low, high);
            }
        }
    }

    private void partition3(int[] array, int low, int high)
            throws Exception
    {
        int i = low - 1;
        int j = high;
        int p = i;
        int q = j;


        for (; ;) {
            while (greater(array, high, ++i)) {
            }

            while (greater(array, --j, high)) {
                if (j == low) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(array, i, j);

            if (equal(array, i, high)) {
                p++;
                swap(array, p, i);
            }
            if (equal(array, j, high)) {
                q--;
                swap(array, q, j);
            }
        }
        unmarkAll();
        swap(array, i, high);

        j = i - 1;
        for (int k = low; k <= p; k++, j--) {
            markBox(k, p);
            swap(array, k, j);
        }
        i = i + 1;
        for (int k = high - 1; k >= q; k--, i++) {
            markBox(q, k);
            swap(array, k, i);
        }

        sort(array, low, j);
        sort(array, i, high);
    }

    

}
